package leetcode.editor.cn;

//Java：寻找两个正序数组的中位数
public class MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        Solution solution = new MedianOfTwoSortedArrays().new Solution();
        double medianSortedArrays = solution.findMedianSortedArrays(new int[]{1, 3, 4, 6, 7}, new int[]{1, 5, 8, 9, 10, 11});
        System.out.println(medianSortedArrays);
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            // 确保nums1是较短的数组
            if (nums1.length > nums2.length) {
                int[] temp = nums1;
                nums1 = nums2;
                nums2 = temp;
            }

            int x = nums1.length;
            int y = nums2.length;

            // 为二分查找设置的边界值
            int low = 0, high = x;

            // 在较短的数组上进行二分查找
            while (low <= high) {
                //nums1的分割线位置
                int partitionX = (low + high) / 2;
                //nums2的分割线位置
                int partitionY = (x + y + 1) / 2 - partitionX;

                // 获取分割线两侧的边缘值
                //nums1分割线位置左侧的值
                int leftValueX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];

                //nums1分割线位置右侧的值
                int rightValueX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];

                //nums2分割线位置左侧的值
                int leftMaxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
                //nums2分割线位置右侧的值
                int rightMinY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];

                // 判断是否找到正确的分割点
                if (leftValueX <= rightMinY && leftMaxY <= rightValueX) {
                    // 计算中位数
                    if ((x + y) % 2 == 0) {
                        return ((double) Math.max(leftValueX, leftMaxY) + Math.min(rightValueX, rightMinY)) / 2;
                    } else {
                        return Math.max(leftValueX, leftMaxY);
                    }
                } else if (leftValueX > rightMinY) {
                    high = partitionX - 1;  // 向左调整
                } else {
                    low = partitionX + 1;   // 向右调整
                }
            }
            return 0.0;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
}